package leetcode.day_2021_04_12_2021_04_18;

import leetcode.day_2020_12_14_12_21.TreeNode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 95. 不同的二叉搜索树 II
 * https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
 * https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/
 */
public class LeetCode0095 {
    Set<String> set = new HashSet<>();
    List<Integer> list = new ArrayList<>();
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        TreeNode root = new TreeNode(0);
        dfs(n, res, root, 0);
        return res;
    }

    // 回溯法
    public void dfs(int n, List<TreeNode> res, TreeNode root, int count) {
        if (count==n && !set.contains(list.toString())) {
            set.add(list.toString());
            TreeNode newRoot = treeCopy(root);
            res.add(newRoot.right);
            return;
        }
        TreeNode root_copy = root;
        for (int i=0; i<=n; i++) {
            root = root_copy;
            while (root != null) {
                if (i < root.val) {
                    if (root.left == null) {
                        root.left = new TreeNode(i);
                        list.add(i);
                        dfs(n, res, root_copy, count+1);
                        root.left = null;
                        list.remove(list.size()-1);
                        break;
                    }
                    root = root.left;
                } else if (i > root.val) {
                    if (root.right == null) {
                        root.right = new TreeNode(i);
                        list.add(i);
                        dfs(n, res, root_copy, count+1);
                        list.remove(list.size()-1);
                        root.right = null;
                        break;
                    }
                    root = root.right;
                } else {
                    break;
                }
            }
        }
    }

    public TreeNode treeCopy(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode node = new TreeNode(root.val);
        if (root.left != null) {
            node.left = treeCopy(root.left);
        }
        if (root.right != null) {
            node.right = root.right;
        }
        return node;
    }

    // 动态规划法
    public List<TreeNode> generateTrees2(int n) {
        ArrayList<TreeNode>[] dp = new ArrayList[n+1];
        dp[0] = new ArrayList<>();
        if (n == 0) {
            return dp[0];
        }
        dp[0].add(null);
        for (int len=1; len<=n; len++) {
            dp[len] = new ArrayList<>();
            for (int rootVal=1; rootVal<=n; rootVal++) {
                int left = rootVal - 1;
                int right = len - rootVal;
                for (TreeNode leftTree : dp[left]) {
                    for (TreeNode rightTree : dp[right]) {
                        TreeNode root = new TreeNode(rootVal);
                        root.left = leftTree;
                        root.right = clone(rightTree, rootVal);
                        dp[len].add(root);
                    }
                }
            }
        }
        return dp[n];
    }

    public TreeNode clone(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        TreeNode node = new TreeNode(root.val + val);
        node.left = clone(root.left, val);
        node.right = clone(root.right, val);
        return node;
    }
}
